package leetcode;

public class BurstBalloons {

	public static void main(String[] args) {
		int[] iNums = {3, 5, 2};
		BurstBalloons object = new BurstBalloons();
		System.out.println(object.maxCoins(iNums));
	}
	
	//We then think can we apply the divide and conquer technique? After all there seems to be many 
	//self similar sub problems from the previous analysis.

	// Well, the nature way to divide the problem is burst one balloon and separate the balloons into 2 sub 
	// sections one on the left and one one the right. 
	// However, in this problem the left and right become adjacent and have effects on the maxCoins in the future.

	// Then another interesting idea come up. Which is quite often seen in dp problem analysis. 
	// That is reverse thinking. Like I said the coins you get for a balloon does not depend on the
	// balloons already burst. Therefore instead of divide the problem by the first balloon to burst, 
	// we divide the problem by the last balloon to burst.

	// Why is that? Because only the first and last balloons we are sure of their adjacent balloons before hand!

	// For the first we have nums[i-1]*nums[i]*nums[i+1] for the last we have nums[-1]*nums[i]*nums[n].

	// OK. Think about n balloons if i is the last one to burst, what now?

	// We can see that the balloons is again separated into 2 sections. But this time since the balloon i is 
	// the last balloon of all to burst, the left and right section now has well defined boundary 
	// and do not affect each other! Therefore we can do either recursive method with memoization or dp.
	// Java D&C with Memoization
	
	public int maxCoins(int[] iNums){
		if(iNums == null || iNums.length <= 0){
			return 0;
		}
		//-1 和  n都是1
		int[] nums = new int[iNums.length + 2];
		
		for (int i = 1; i < nums.length - 1; i++) {
			nums[i] = iNums[i - 1];
		}
		nums[0] = nums[nums.length - 1] = 1;
		
		int[][] memorization = new int[nums.length][nums.length];
		
		return burst(memorization, nums, 0, nums.length - 1);
	}
	
	public int burst(int[][] memorization, int[] nums, int left, int right){
		
		//因为我们的长度是n + 2,也就是意味着长度大于等于3才可以爆破，只剩下两个的时候表示无ballon可以burst
		if (left + 1 == right) return 0;
		
		//如果之前计算过，直接返回，避免了重复的计算
		if (memorization[left][right] > 0) return memorization[left][right];
		
		int ans = 0;
		
		//依次枚举以i结尾的所有可能
		for(int i = left + 1; i < right; i++){
			//计算爆破i的值，然后分别计算左右两边的值
			//因为i是最后一个爆破的，也就是意味着i应该乘以left和right
			int cur = nums[i] * nums[left] * nums[right];
			ans = Math.max(ans, cur + burst(memorization, nums, left, i) + burst(memorization, nums, i, right));
			
			System.out.println("left: " + left + " right: " + right + "  " + (ans - cur));
		}
		memorization[left][right] = ans;
		
		return ans;
	}
	
	
	//java dp
	public int maxCoins_dp(int[] iNums) {
	    int[] nums = new int[iNums.length + 2];
	    //-1 和  n都是1
	  	for (int i = 1; i < nums.length - 1; i++) {
	  		nums[i] = iNums[i - 1];
	  	}
	  	nums[0] = nums[nums.length - 1] = 1;
	  		
	  	int[][] dp = new int[nums.length][nums.length];

	  	int n = nums.length;
	    for (int k = 2; k < n; ++k){
	        for (int left = 0; left < n - k; ++left) {
	            int right = left + k;
	            //left和right为边界
	            for (int i = left + 1; i < right; ++i)
	            	
	            	//感觉这个dp挺不好理解的，相比之下递归加记忆化搜索很好理解
	            	//dp[left][i]是左边的结果, dp[i][right]是右边的结果
	                dp[left][right] = Math.max(dp[left][right], 
	                nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
	        }
	    }
	    return dp[0][n - 1];
	}
}
